

<!DOCTYPE html>
<html lang="zh-CN" data-default-color-scheme=&#34;light&#34;>



<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="https://cdn.jsdelivr.net/gh/kzwrime/kzwrime.github.io/img/favicon.png">
  <link rel="icon" type="image/png" href="https://tuchuangrrr.oss-cn-shenzhen.aliyuncs.com/img/kunnan.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="">
  <meta name="author" content="霜华">
  <meta name="keywords" content="">
  <title>图论中的重要算法 - kunzh</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/lib/hint/hint.min.css" />

  
    
    
      
      <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/atelier-lakeside-dark.min.css" />
    
  

  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_pf9vaxs7x7b.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_kmeydafke9r.css">


<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script  src="/js/utils.js" ></script>
  <script  src="/js/color-schema.js" ></script>
</head>


<body>
  <header style="height: 60vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>kunzh</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/links/">
                <i class="iconfont icon-link-fill"></i>
                友链
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/shuoshuo2/">
                <i class="iconfont icon-speakernotes"></i>
                留言板
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;</a>
          </li>
        
        
          <li class="nav-item" id="color-toggle-btn">
            <a class="nav-link" href="javascript:">&nbsp;<i
                class="iconfont icon-dark" id="color-toggle-icon"></i>&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="banner intro-2" id="background" parallax=true
         style="background: url('https://rainrime.top/img/SloveniaAlps.jpg') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container page-header text-center fade-in-up">
            <span class="h2" id="subtitle">
              
            </span>

            
              <div class="mt-3">
  
  
    <span class="post-meta">
      <i class="iconfont icon-date-fill" aria-hidden="true"></i>
      <time datetime="2020-06-05 12:00" pubdate>
        2020年6月5日 中午
      </time>
    </span>
  
</div>

<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      1.2k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      16
       分钟
    </span>
  

  
  
    
      <!-- LeanCloud 统计文章PV -->
      <span id="leancloud-post-views-container" class="post-meta" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="leancloud-post-views"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <article class="post-content mx-auto" id="post">
            <!-- SEO header -->
            <h1 style="display: none">图论中的重要算法</h1>
            
            <div class="markdown-body" id="post-body">
              <h1 id="图论中的重要算法"><a class="markdownIt-Anchor" href="#图论中的重要算法"></a> 图论中的重要算法</h1>
<h2 id="遍历"><a class="markdownIt-Anchor" href="#遍历"></a> 遍历</h2>
<h3 id="dfs"><a class="markdownIt-Anchor" href="#dfs"></a> DFS</h3>
<p>深度优先搜索（Depth-first-search，DFS）</p>
<pre><code class="hljs delphi"><span class="hljs-comment">// 简单描述</span>
<span class="hljs-function"><span class="hljs-keyword">procedure</span> <span class="hljs-title">DFS</span><span class="hljs-params">(G：带有顶点v_1,v_2...v_n的连通图)</span></span>
<span class="hljs-function">	<span class="hljs-title">T</span>:</span>= 只包含顶点v_1的树
	visit(v_i)

<span class="hljs-function"><span class="hljs-keyword">procedure</span> <span class="hljs-title">visit</span><span class="hljs-params">(v：G的顶点)</span></span>
<span class="hljs-function">	<span class="hljs-title">for</span> 与<span class="hljs-title">v</span>相邻且还不在<span class="hljs-title">T</span>中的每个顶点ω</span>
<span class="hljs-function">		加入顶点ω和边<span class="hljs-comment">&#123;v,ω&#125;</span>到<span class="hljs-title">T</span></span>
<span class="hljs-function">		<span class="hljs-title">visit</span><span class="hljs-params">(ω)</span></span></code></pre>
<pre><code class="hljs c"><span class="hljs-function">function <span class="hljs-title">DFS</span><span class="hljs-params">( Start , Goal )</span></span>
<span class="hljs-function">	<span class="hljs-title">push</span><span class="hljs-params">(Stack , Start )</span></span>;
	<span class="hljs-keyword">while</span> ( Stack is <span class="hljs-keyword">not</span> empty )
		var Node := Pop( Stack );
		<span class="hljs-keyword">if</span> ( Visited (Node) ) 
			<span class="hljs-keyword">continue</span> ; <span class="hljs-comment">//C style continue</span>
		<span class="hljs-keyword">if</span> ( Node = Goal )
			<span class="hljs-keyword">return</span> Node ;
		setVisited (Node );
		<span class="hljs-function"><span class="hljs-keyword">for</span> Child in <span class="hljs-title">Expand</span><span class="hljs-params">(Node)</span></span>
<span class="hljs-function">			<span class="hljs-title">if</span> <span class="hljs-params">( notVisited (Node) )</span></span>
<span class="hljs-function">				<span class="hljs-title">push</span> <span class="hljs-params">(Stack , Child )</span></span>;</code></pre>
<!-- ![DFS(1)(1)](/img/图论中的重要算法/DFS(1)(1).gif) -->
<p><img src="https://cdn.jsdelivr.net/gh/kzwrime/kzwrime.github.io/img/图论中的重要算法/DFS(1)(1).gif" srcset="/img/loading.gif" alt="DFS(1)(1)" width="75%" /></p>
<h3 id="bfs"><a class="markdownIt-Anchor" href="#bfs"></a> BFS</h3>
<p>广度优先搜索（Breadth-first-search，BFS）</p>
<pre><code class="hljs cal"><span class="hljs-function"><span class="hljs-keyword">procedure</span> <span class="hljs-title">BFS</span><span class="hljs-params">(G：带顶点v_1,v_2...v_n的连通图)</span></span>
<span class="hljs-function">    <span class="hljs-title">T</span>:</span>= 只包含顶点v_1的树
    L:= 空表
    把v1放入尚未处理的顶点的表L中
    <span class="hljs-keyword">while</span> L 非空
    	删除L中第一个顶点v
    	<span class="hljs-keyword">for</span> v的每个邻居ω
    		<span class="hljs-keyword">if</span> ω即不再L中也不在T中 <span class="hljs-keyword">then</span>
    			加入ω到L的末尾c
    			加入ω和边&#123;v,ω&#125;到T</code></pre>
<pre><code class="hljs c"><span class="hljs-function">function <span class="hljs-title">BFS</span><span class="hljs-params">( Start , Goal )</span> </span>
<span class="hljs-function">	<span class="hljs-title">setVisited</span> <span class="hljs-params">( Start )</span></span>; 
	enqueue (Queue , Start ); 
		<span class="hljs-keyword">while</span> ( notEmpty(Queue) )
			Node := dequeue (Queue ); 
			<span class="hljs-keyword">if</span> ( Node = Goal )
				<span class="hljs-keyword">return</span> Node ; 
			<span class="hljs-function"><span class="hljs-keyword">for</span> each Child in <span class="hljs-title">Expand</span><span class="hljs-params">(Node)</span></span>
<span class="hljs-function">				<span class="hljs-title">if</span> <span class="hljs-params">( notVisited ( Child ) )</span></span>
<span class="hljs-function">					<span class="hljs-title">setVisited</span> <span class="hljs-params">( Child )</span></span>; 
					enqueue (Queue , Child );</code></pre>
<!-- ![BFS(1)(1)](/img/图论中的重要算法/BFS(1)(1).gif) -->
<p><img src="https://rainrime.top/img/图论中的重要算法/BFS(1)(1).gif" srcset="/img/loading.gif" alt="BFS(1)(1)" width="75%" /></p>
<h2 id="mstminimum-spanning-tree"><a class="markdownIt-Anchor" href="#mstminimum-spanning-tree"></a> MST(Minimum Spanning Tree)</h2>
<p>已知：<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>G</mi><mo>=</mo><mo>&lt;</mo><mi>V</mi><mo separator="true">,</mo><mi>E</mi><mo separator="true">,</mo><mi>ω</mi><mo>&gt;</mo></mrow><annotation encoding="application/x-tex">G=&lt;V,E,ω&gt;</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault">G</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span></span><span class="base"><span class="strut" style="height:0.5782em;vertical-align:-0.0391em;"></span><span class="mrel">&lt;</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.8777699999999999em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.22222em;">V</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault" style="margin-right:0.05764em;">E</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">ω</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">&gt;</span></span></span></span>是无向连通赋权图，其中V是点集，E是边集，ω 是<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>E</mi><mo>→</mo><msup><mi mathvariant="double-struck">R</mi><mo>+</mo></msup></mrow><annotation encoding="application/x-tex">E \rightarrow \mathbb{R}^+</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.05764em;">E</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">→</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.771331em;vertical-align:0em;"></span><span class="mord"><span class="mord"><span class="mord mathbb">R</span></span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.771331em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mbin mtight">+</span></span></span></span></span></span></span></span></span></span></span>的单射函数，T为G的生成树，T的所有边的权值之和称为T的权值。</p>
<p>若T在G中的所有生成树中的权值最小，称为最小生成树。</p>
<p>最小生成树的实际应用有很多，例如可以把以下的图视作各个城市和他们之间的距离，想要铺设总路程最短的光纤/高速连接他们，也就是求出这个图的一个最小生成树，图中加粗形成的树即为所求。</p>
<!-- ![Minimum_spanning_tree](/img/图论中的重要算法/Minimum_spanning_tree.svg) -->
<p><img src="https://rainrime.top/img/图论中的重要算法/Minimum_spanning_tree.svg" srcset="/img/loading.gif" alt="Minimum_spanning_tree.svg" width="75%" /></p>
<h3 id="prim"><a class="markdownIt-Anchor" href="#prim"></a> Prim</h3>
<p>普林算法（Prim’s Algorithm）</p>
<pre><code class="hljs c"><span class="hljs-function">procedure <span class="hljs-title">Prim</span><span class="hljs-params">(G=&lt;V,E,ω&gt;)</span></span>
<span class="hljs-function">	T:</span>=权值最小的边;
	<span class="hljs-keyword">for</span> i:=<span class="hljs-number">1</span> to n<span class="hljs-number">-2</span>
		e:= 与T相邻且T+&#123;e&#125;没有回路的最小权值边
		T:= T+&#123;e&#125;
	<span class="hljs-keyword">return</span> T</code></pre>
<!-- ![prim](/img/图论中的重要算法/prim-1591949176159.gif) -->
<p><img src="https://rainrime.top/img/图论中的重要算法/prim-1591949176159.gif" srcset="/img/loading.gif" alt="prim-1591949176159.gif" width="75%" /></p>
<p><img src="https://rainrime.top/img/%E5%9B%BE%E8%AE%BA%E4%B8%AD%E7%9A%84%E9%87%8D%E8%A6%81%E7%AE%97%E6%B3%95/PrimAlgDemo.gif" srcset="/img/loading.gif" alt="PrimAlgDemo" /></p>
<!-- <p><img src="/img/图论中的重要算法/PrimAlgDemo.gif" srcset="/img/loading.gif" alt="PrimAlgDemo.gif" width="60%" /></p> -->
<h3 id="kruskal"><a class="markdownIt-Anchor" href="#kruskal"></a> Kruskal</h3>
<p>克鲁斯托尔算法（Kruskal’s Algorithm）</p>
<pre><code class="hljs c"><span class="hljs-function">procedure <span class="hljs-title">Kruskal</span><span class="hljs-params">(G=&lt;V,E,ω&gt;)</span></span>
<span class="hljs-function">	T:</span>= 空集（图）
	E:= &#123;e_1,e_2...e_n&#125;(ω(e_1)&lt;ω(e_2)&lt;...&lt;ω(e_n))
	<span class="hljs-keyword">for</span> i:=<span class="hljs-number">1</span> to n<span class="hljs-number">-1</span>
		<span class="hljs-keyword">if</span> ( T+&#123;e_i&#125; 不构成回路 )
			T:= T + &#123;e_i&#125;
	<span class="hljs-keyword">return</span> T</code></pre>
<!-- ![Krustal(1)(1)](/img/图论中的重要算法/Krustal(1)(1).gif) -->
<p><img src="https://rainrime.top/img/图论中的重要算法/Krustal(1)(1).gif" srcset="/img/loading.gif" alt="Krustal(1)(1).gif" width="75%" /></p>
<p><img src="https://rainrime.top/img/图论中的重要算法/MST_kruskal_en.gif" srcset="/img/loading.gif"  align="middle" height="300" /></p>
<h3 id="sollin"><a class="markdownIt-Anchor" href="#sollin"></a> Sollin</h3>
<p>索林算法（Sollin’s Algorithm）</p>
<p><img src="https://rainrime.top/img/%E5%9B%BE%E8%AE%BA%E4%B8%AD%E7%9A%84%E9%87%8D%E8%A6%81%E7%AE%97%E6%B3%95/Boruvka's_algorithm_(Sollin's_algorithm)_Anim.gif" srcset="/img/loading.gif" alt="Boruvka's_algorithm_(Sollin's_algorithm)_Anim" /></p>
<!-- <p><img src="/img/图论中的重要算法/Boruvka's_algorithm_(Sollin's_algorithm)_Anim.gif" srcset="/img/loading.gif" alt="Boruvka's_algorithm_(Sollin's_algorithm)_Anim.gif" width="95%" /></p> -->
<h2 id="最短路径"><a class="markdownIt-Anchor" href="#最短路径"></a> 最短路径</h2>
<p><a target="_blank" rel="noopener" href="http://www.webhek.com/post/pathfinding.html">http://www.webhek.com/post/pathfinding.html</a></p>
<h3 id="dilkstra"><a class="markdownIt-Anchor" href="#dilkstra"></a> Dilkstra</h3>
<p>迪斯克斯拉算法（Dilkstra’s Algorithm）</p>
<p>迪斯克斯拉算法本质为贪心算法，在已有的图外加上最近的点k形成新图，然后更新图外每个点的值，直到到达这个点。如图：</p>
<!-- ![Dijkstra_Animation](../img/图论中的重要算法/Dijkstra_Animation.gif) -->
<p><img src="https://rainrime.top/img/图论中的重要算法/Dijkstra_Animation.gif" srcset="/img/loading.gif" alt="Dijkstra_Animation" width="75%" /></p>
<p>这个是平面直角坐标的情形。</p>
<!-- ![Dijkstras_progress_animation](/img/图论中的重要算法/Dijkstras_progress_animation.gif) -->
<p><img src="https://rainrime.top/img/图论中的重要算法/Dijkstras_progress_animation.gif" srcset="/img/loading.gif" alt="Dijkstras_progress_animation" width="75%" /></p>
<p>伪代码描述如下：</p>
<p><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi mathvariant="normal">注</mi><mi mathvariant="normal">：</mi><mi mathvariant="normal">已</mi><mi mathvariant="normal">知</mi><mi>G</mi><mi mathvariant="normal">为</mi><mi mathvariant="normal">简</mi><mi mathvariant="normal">单</mi><mi mathvariant="normal">带</mi><mi mathvariant="normal">正</mi><mi mathvariant="normal">权</mi><mi mathvariant="normal">连</mi><mi mathvariant="normal">通</mi><mi mathvariant="normal">图</mi><mi mathvariant="normal">，</mi><mo stretchy="false">(</mo><msub><mi>v</mi><mi>i</mi></msub><mo separator="true">,</mo><msub><mi>v</mi><mi>j</mi></msub><mo stretchy="false">)</mo><mi mathvariant="normal">∉</mi><mi>E</mi><mo>⇔</mo><mi>ω</mi><mo stretchy="false">(</mo><msub><mi>v</mi><mi>i</mi></msub><mo separator="true">,</mo><msub><mi>v</mi><mi>j</mi></msub><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="normal">∞</mi></mrow><annotation encoding="application/x-tex">注：已知G为简单带正权连通图，(v_i,v_j) \notin E \Leftrightarrow ω(v_i,v_j)=\infty 
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.036108em;vertical-align:-0.286108em;"></span><span class="mord cjk_fallback">注</span><span class="mord cjk_fallback">：</span><span class="mord cjk_fallback">已</span><span class="mord cjk_fallback">知</span><span class="mord mathdefault">G</span><span class="mord cjk_fallback">为</span><span class="mord cjk_fallback">简</span><span class="mord cjk_fallback">单</span><span class="mord cjk_fallback">带</span><span class="mord cjk_fallback">正</span><span class="mord cjk_fallback">权</span><span class="mord cjk_fallback">连</span><span class="mord cjk_fallback">通</span><span class="mord cjk_fallback">图</span><span class="mord cjk_fallback">，</span><span class="mopen">(</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.03588em;">v</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:-0.03588em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.03588em;">v</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:-0.03588em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><span class="mord"><span class="mrel">∈</span></span><span class="mord"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.75em;"><span style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="llap"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="inner"><span class="mord"><span class="mord">/</span><span class="mspace" style="margin-right:0.05555555555555555em;"></span></span></span><span class="fix"></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.25em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.05764em;">E</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">⇔</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.036108em;vertical-align:-0.286108em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">ω</span><span class="mopen">(</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.03588em;">v</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:-0.03588em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.03588em;">v</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:-0.03588em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord">∞</span></span></span></span></span></p>
<pre><code class="hljs c"><span class="hljs-function">procedure <span class="hljs-title">Dijkstra</span><span class="hljs-params">(G)</span></span>
<span class="hljs-function">    <span class="hljs-keyword">for</span> i:</span>=<span class="hljs-number">1</span> to n
        L(v[i]):= MAX
    L(a):= <span class="hljs-number">0</span>
    S:= NULLbushuyu
    <span class="hljs-keyword">while</span> (!(z ∈ S))
		u:= 不属于S的L(u)最小的一个顶点
  		S:= S ∪ &#123;u&#125;
		<span class="hljs-keyword">for</span> v <span class="hljs-keyword">not</span> in S
			<span class="hljs-keyword">if</span> (L(u) + ω(u,v) &lt; L(v))
				L(v):= L(u) + ω(u,v)
	<span class="hljs-keyword">return</span> L(z)</code></pre>
<h3 id="floyd-warshall"><a class="markdownIt-Anchor" href="#floyd-warshall"></a> Floyd-Warshall</h3>
<p>弗洛伊德-沃舍尔 全源最短路径算法</p>
<p>弗洛伊德算法本质上为动态规划算法，对于每两个点，计算能否借助第三个点达成更短路径。</p>
<p>此算法解决了迪斯克斯拉算法无法处理负权值的边的问题，但由于要计算全部更适合求出全部最短路径。需要注意的是，此算法不检测负权环，要求图本身不带有负权环或手动处理，不然在负权环一圈圈绕路程越来越短。。。</p>
<p>以此图为例，图中的k为路径的边数，分别计算边数为0、1、2、3时的最短路径，k=1时更新了2-&gt;3的长度，以此类推，由传递闭包的特性最多求到k=v-1即可。</p>
<!-- ![Floyd-Warshall_example](/img/图论中的重要算法/Floyd-Warshall_example.svg) -->
<p><img src="https://rainrime.top/img/图论中的重要算法/Floyd-Warshall_example.svg" srcset="/img/loading.gif" alt="Floyd-Warshall_example.svg" width="95%" /></p>
<p>用伪代码简要描述算法如下</p>
<p><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi mathvariant="normal">注</mi><mi mathvariant="normal">：</mi><mi mathvariant="normal">已</mi><mi mathvariant="normal">知</mi><mi>G</mi><mi mathvariant="normal">为</mi><mi mathvariant="normal">简</mi><mi mathvariant="normal">单</mi><mi mathvariant="normal">带</mi><mi mathvariant="normal">权</mi><mi mathvariant="normal">连</mi><mi mathvariant="normal">通</mi><mi mathvariant="normal">图</mi><mi mathvariant="normal">，</mi><mo stretchy="false">(</mo><msub><mi>v</mi><mi>i</mi></msub><mo separator="true">,</mo><msub><mi>v</mi><mi>j</mi></msub><mo stretchy="false">)</mo><mi mathvariant="normal">∉</mi><mi>E</mi><mo>⇔</mo><mi>ω</mi><mo stretchy="false">(</mo><msub><mi>v</mi><mi>i</mi></msub><mo separator="true">,</mo><msub><mi>v</mi><mi>j</mi></msub><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="normal">∞</mi></mrow><annotation encoding="application/x-tex">注：已知G为简单带权连通图，(v_i,v_j) \notin E \Leftrightarrow ω(v_i,v_j)=\infty  
</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.036108em;vertical-align:-0.286108em;"></span><span class="mord cjk_fallback">注</span><span class="mord cjk_fallback">：</span><span class="mord cjk_fallback">已</span><span class="mord cjk_fallback">知</span><span class="mord mathdefault">G</span><span class="mord cjk_fallback">为</span><span class="mord cjk_fallback">简</span><span class="mord cjk_fallback">单</span><span class="mord cjk_fallback">带</span><span class="mord cjk_fallback">权</span><span class="mord cjk_fallback">连</span><span class="mord cjk_fallback">通</span><span class="mord cjk_fallback">图</span><span class="mord cjk_fallback">，</span><span class="mopen">(</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.03588em;">v</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:-0.03588em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.03588em;">v</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:-0.03588em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel"><span class="mord"><span class="mrel">∈</span></span><span class="mord"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.75em;"><span style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="llap"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="inner"><span class="mord"><span class="mord">/</span><span class="mspace" style="margin-right:0.05555555555555555em;"></span></span></span><span class="fix"></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.25em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.05764em;">E</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">⇔</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:1.036108em;vertical-align:-0.286108em;"></span><span class="mord mathdefault" style="margin-right:0.03588em;">ω</span><span class="mopen">(</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.03588em;">v</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.31166399999999994em;"><span style="top:-2.5500000000000003em;margin-left:-0.03588em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">i</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.16666666666666666em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.03588em;">v</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:-0.03588em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.43056em;vertical-align:0em;"></span><span class="mord">∞</span></span></span></span></span></p>
<pre><code class="hljs c"><span class="hljs-function">procedure <span class="hljs-title">Floyd</span> <span class="hljs-params">(G)</span></span>
<span class="hljs-function">    <span class="hljs-keyword">for</span> i:</span>= <span class="hljs-number">1</span> to n
        <span class="hljs-keyword">for</span> j:= <span class="hljs-number">1</span> to n
            d(v[i], v[j]) := w(v[i], v[j])
    <span class="hljs-keyword">for</span> i:= <span class="hljs-number">1</span> to n
        <span class="hljs-keyword">for</span> j:= <span class="hljs-number">1</span> to n
            <span class="hljs-keyword">for</span> k:= <span class="hljs-number">1</span> to n
                <span class="hljs-keyword">if</span> ( d(v[j], v[i]) + d(v[i], v[k]) &lt; d(v[j], v[k]) )
                    d(v[j], v[k]):= d(v[j], v[i]) + d(v[i], v[k])
    <span class="hljs-keyword">return</span> d(v[i], v[j])</code></pre>
<h3 id="a"><a class="markdownIt-Anchor" href="#a"></a> A*</h3>
<!-- ![Astar_progress_animation](/img/图论中的重要算法/Astar_progress_animation.gif) -->
<p><img src="https://rainrime.top/img/图论中的重要算法/Astar_progress_animation.gif" srcset="/img/loading.gif" alt="Astar_progress_animation.gif" width="75%" /></p>
<!-- ![AstarExampleEn](/img/图论中的重要算法/AstarExampleEn.gif) -->
<p><img src="https://rainrime.top/img/图论中的重要算法/AstarExampleEn.gif" srcset="/img/loading.gif" alt="AstarExampleEn.gif" width="75%" /></p>
<p class="note note-info">部分图源网络，其版权归原作者所有</p>
            </div>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/categories/%E7%AE%97%E6%B3%95/">算法</a>
                    
                  </div>
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/tags/%E7%AE%97%E6%B3%95/">算法</a>
                    
                      <a class="hover-with-bg" href="/tags/%E5%9B%BE%E8%AE%BA/">图论</a>
                    
                  </div>
                
              </div>
              
              
                <div class="post-prevnext row">
                  <article class="post-prev col-6">
                    
                    
                      <a href="/2020/06/vscode%20+%20ssh%20+%20c_cpp/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">vscode + ssh + c/cpp</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </article>
                  <article class="post-next col-6">
                    
                    
                      <a href="/2020/06/More%20exercise%2001/">
                        <span class="hidden-mobile">More exercise 01</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </article>
                </div>
              
            </div>

            
              <!-- Comments -->
              <article class="comments" id="comments">
                
                
  <div id="vcomments"></div>
  <script type="text/javascript">
    function loadValine() {
      addScript('https://cdn.staticfile.org/valine/1.4.14/Valine.min.js', function () {
        new Valine({
          el: "#vcomments",
          app_id: "iAgkjaR2s2ws1XXtS5sVxE7H-MdYXbMMI",
          app_key: "vKka6XRlblVTkbKz8jLXx6EQ",
          placeholder: "你是来自评论区的小惊喜吗 ...",
          path: window.location.pathname,
          avatar: "retro",
          meta: ["nick","mail"],
          pageSize: "10",
          lang: "zh-CN",
          highlight: false,
          recordIP: true,
          serverURLs: "",
        });
      });
    }
    waitElementVisible('vcomments', loadValine);
  </script>
  <noscript>Please enable JavaScript to view the <a target="_blank" href="https://valine.js.org" rel="nofollow noopener noopener">comments
      powered by Valine.</a></noscript>


<!-- 
  <div id="vcomments"></div>
  <script type="text/javascript">
    function loadValine() {
      addScript('https://cdn.staticfile.org/valine/1.4.14/Valine.min.js', function () {
        new Valine({
          el: "#vcomments",
          enableQQ: true,
          boolean: true,
          app_id: "iAgkjaR2s2ws1XXtS5sVxE7H-MdYXbMMI",
          app_key: "vKka6XRlblVTkbKz8jLXx6EQ",
          placeholder: "你是来自评论区的小惊喜吗 ...",
          path: "window.location.pathname",
          avatar: "retro",
          meta: "["nick","mail"]",
          pageSize: "10",
          lang: "zh-CN",
          highlight: false,
          recordIP: true,
          serverURLs: "",
            // 设置Bilibili表情包地址
            emojiCDN: '//i0.hdslb.com/bfs/emote/', 
            // 表情title和图片映射
            emojiMaps: {
            "tv_doge": "6ea59c827c414b4a2955fe79e0f6fd3dcd515e24.png",
            "tv_亲亲": "a8111ad55953ef5e3be3327ef94eb4a39d535d06.png",
            "tv_偷笑": "bb690d4107620f1c15cff29509db529a73aee261.png",
            "tv_再见": "180129b8ea851044ce71caf55cc8ce44bd4a4fc8.png",
            "tv_冷漠": "b9cbc755c2b3ee43be07ca13de84e5b699a3f101.png",
            "tv_发怒": "34ba3cd204d5b05fec70ce08fa9fa0dd612409ff.png",
            "tv_发财": "34db290afd2963723c6eb3c4560667db7253a21a.png",
            "tv_可爱": "9e55fd9b500ac4b96613539f1ce2f9499e314ed9.png",
            "tv_吐血": "09dd16a7aa59b77baa1155d47484409624470c77.png",
            "tv_呆": "fe1179ebaa191569b0d31cecafe7a2cd1c951c9d.png",
            "tv_呕吐": "9f996894a39e282ccf5e66856af49483f81870f3.png",
            "tv_困": "241ee304e44c0af029adceb294399391e4737ef2.png",
            "tv_坏笑": "1f0b87f731a671079842116e0991c91c2c88645a.png",
            "tv_大佬": "093c1e2c490161aca397afc45573c877cdead616.png",
            "tv_大哭": "23269aeb35f99daee28dda129676f6e9ea87934f.png",
            "tv_委屈": "d04dba7b5465779e9755d2ab6f0a897b9b33bb77.png",
            "tv_害羞": "a37683fb5642fa3ddfc7f4e5525fd13e42a2bdb1.png",
            "tv_尴尬": "7cfa62dafc59798a3d3fb262d421eeeff166cfa4.png",
            "tv_微笑": "70dc5c7b56f93eb61bddba11e28fb1d18fddcd4c.png",
            "tv_思考": "90cf159733e558137ed20aa04d09964436f618a1.png",
            "tv_惊吓": "0d15c7e2ee58e935adc6a7193ee042388adc22af.png",
            "tv_打脸": "56ab10b624063e966bfcb76ea5dc4794d87dfd47.png",
            "tv_抓狂": "fe31c08edad661d63762b04e17b8d5ae3c71a757.png",
            "tv_抠鼻": "c666f55e88d471e51bbd9fab9bb308110824a6eb.png",
            "tv_斜眼笑": "911f987aa8bc1bee12d52aafe62bc41ef4474e6c.png",
            "tv_无奈": "ea8ed89ee9878f2fece2dda0ea8a5dbfe21b5751.png",
            "tv_晕": "5443c22b4d07fb1907ccc610c8e6db254f2461b7.png",
            "tv_流汗": "cead1c351ab8d79e9f369605beb90148db0fbed3.png",
            "tv_流泪": "7e71cde7858f0cd50d74b0264aa26db612a8a167.png",
            "tv_流鼻血": "c32d39db2737f89b904ca32700d140a9241b0767.png",
            "tv_点赞": "f85c354995bd99e28fc76c869bfe42ba6438eff4.png",
            "tv_生气": "26702dcafdab5e8225b43ffd23c94ac1ff932654.png",
            "tv_生病": "8b0ec90e6b86771092a498c54f09fc94621c1900.png",
            "tv_疑问": "0793d949b18d7be716078349c202c15ff166f314.png",
            "tv_白眼": "c1d59f439e379ee50eef488bcb5e5378e5044ea4.png",
            "tv_皱眉": "72ccad6679fea0d14cce648b4d818e09b8ffea2d.png",
            "tv_目瞪口呆": "0b8cb81a68de5d5365212c99375e7ace3e7891b7.png",
            "tv_睡着": "8b196675b53af58264f383c50ad0945048290b33.png",
            "tv_笑哭": "1abc628f6d4f4caf9d0e7800878f4697abbc8273.png",
            "tv_腼腆": "89712c0d4af73e67f89e35cbc518420380a7f6f4.png",
            "tv_色": "61822c7e9aae5da76475e7892534545336b23a6f.png",
            "tv_调侃": "4bc022533ef31544ca0d72c12c808cf4a1cce3e3.png",
            "tv_调皮": "b9c41de8e82dd7a8515ae5e3cb63e898bf245186.png",
            "tv_鄙视": "6e72339f346a692a495b123174b49e4e8e781303.png",
            "tv_闭嘴": "c9e990da7f6e93975e25fd8b70e2e290aa4086ef.png",
            "tv_难过": "87f46748d3f142ebc6586ff58860d0e2fc8263ba.png",
            "tv_馋": "fc7e829b845c43c623c8b490ee3602b7f0e76a31.png",
            "tv_鬼脸": "0ffbbddf8a94d124ca2f54b360bbc04feb6bbfea.png",
            "tv_黑人问号": "45821a01f51bc867da9edbaa2e070410819a95b2.png",
            "tv_鼓掌": "1d21793f96ef4e6f48b23e53e3b9e42da833a0f6.png"
                // ... 更多表情
            }
        });
      });
    }
    createObserver(loadValine, 'vcomments');
  </script>
      <style>
        #vcomments textarea {
            box-sizing: border-box;
            background: url("/img/v2-f3d5c26e7ac0da80ee72b6dc178d6aa1_b005.gif") 100% 100% no-repeat;
        }
      </style>
  <noscript>Please enable JavaScript to view the <a target="_blank" href="https://valine.js.org" rel="nofollow noopener noopener">comments
      powered by Valine.</a></noscript>
 -->

              </article>
            
          </article>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->

  <div class="col-lg-7 mx-auto nopadding-md">
    <div class="container custom post-content mx-auto">
      <img src="/img/371905140-ROBOT-WAVING-400px-unscreen(1).gif" srcset="/img/loading.gif" class="rounded mx-auto d-block mt-5" style="width:200px; height:200px;" >
    </div>
  </div>


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a>
      <i class="iconfont icon-love"></i>
      <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener">
        <span>Fluid</span></a>
        <br>
        <span>©2019 - 2020 By</span>
        <a href="https://github.com/rainrime" target="_blank" rel="nofollow noopener"><span>kunzh</span></a>
    </div>
    
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


    

    
  </div>
</footer>


<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/js/debouncer.js" ></script>
<script  src="/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/js/lazyload.js" ></script>
  



  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/js/clipboard-use.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>





  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: '#post-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 6,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "图论中的重要算法&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script  src="https://cdn.staticfile.org/anchor-js/4.2.2/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "hover",
      
      icon: "❡"
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script  src="/js/local-search.js" ></script>
  <script>
    var path = "/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>





  

  
    <!-- KaTeX -->
    <link  rel="stylesheet" href="https://cdn.staticfile.org/KaTeX/0.11.1/katex.min.css" />
  



  
  
    <script type="text/javascript">
      //定义获取词语下标
      var a_idx = 0;
      jQuery(document).ready(function ($) {
        //点击body时触发事件
        $("body").click(function (e) {
          //需要显示的词语
          var a = new Array("富强", "民主", "文明", "和谐", "自由", "平等", "公正", "法治", "爱国", "敬业", "诚信", "友善");
          //设置词语给span标签
          var $i = $("<span/>").text(a[a_idx]);
          //下标等于原来下标+1  余 词语总数
          a_idx = (a_idx + 1) % a.length;
          //获取鼠标指针的位置，分别相对于文档的左和右边缘。
          //获取x和y的指针坐标
          var x = e.pageX, y = e.pageY;
          //在鼠标的指针的位置给$i定义的span标签添加css样式
          $i.css({
            "z-index": 999,
            "top": y - 20,
            "left": x,
            "position": "absolute",
            "font-weight": "bold",
            "color": rand_color()
          });
          // 随机颜色
          function rand_color() {
            return "rgb(" + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + ")"
          }
          //在body添加这个标签
          $("body").append($i);
          //animate() 方法执行 CSS 属性集的自定义动画。
          //该方法通过CSS样式将元素从一个状态改变为另一个状态。CSS属性值是逐渐改变的，这样就可以创建动画效果。
          //详情请看http://www.w3school.com.cn/jquery/effect_animate.asp
          $i.animate({
            //将原来的位置向上移动180
            "top": y - 180,
            "opacity": 0
            //1500动画的速度
          }, 1500, function () {
            //时间到了自动删除
            $i.remove();
          });
        });
      })
      ;
    </script>
  



  <script>(function (i, s, o, g, r, a, m) {
      i['DaoVoiceObject'] = r;
      i[r] = i[r] ||
        function () {
          (i[r].q = i[r].q || []).push(arguments);
        };
      i[r].l = 1 * new Date();
      a = s.createElement(o);
      m = s.getElementsByTagName(o)[0];
      a.async = 1;
      a.src = g;
      a.charset = 'utf-8';
      m.parentNode.insertBefore(a, m);
    })(window, document, 'script', ('https:' === document.location.protocol ? 'https:' : 'http:') + "//widget.daovoice.io/widget/244aa65c.js", 'daovoice');
    daovoice('init', {
      app_id: "244aa65c",
    });
    daovoice('update');
  </script>









  

  

  

  

  

  





</body>
</html>
